//图的邻接链表结构体实现(顺序 + 链式存储)，空间复杂度：有向图O(|V|+|E|)，无向图O(|V|+2|E|)

#include <cstdlib>

#define MaxVertexNum 100  //图中顶点数目的最大值
#define MAX_WEIGHT 0Xffff //边的最大权重
typedef int VertexType;   //顶点数据类型
typedef int EdgeType;     //带权图中边上权值的数据类型 (非带权图的边的权值为1)

typedef struct ArcNode //边表结点
{
    EdgeType weight;                //该弧(边)的权值
    VertexType adjvex;              //该弧所指向的顶点，即弧尾的顶点(顶点号)
    struct ArcNode *next = nullptr; //指向下一个邻接结点(实际是一个边表节点)
} ArcNode;

typedef struct VNode //顶点表结点
{
    VertexType vertex;        //顶点的结点值(这里为方便实现就直接用数字[即顶点号]代替了，按理说是可以为任意类型的)
    ArcNode *first = nullptr; //指向第一个依附源结点的边表结点
} VNode, AdjList[MaxVertexNum];

typedef struct
{
    bool DirStatue = false; // false代表该图为无向图；true代表该图为有向图
    AdjList vertexes;       //邻接表(顶点表)(所有顶点拉出的链表集合且所有链表的顶点在同一个数组上)。 AdjList vertexes; <=> VNode vertexes[MaxVertexNum];
    int vexnum, arcnum;     //图的顶点数和弧数
} ALGraph;                  // ALGraph是以邻接表存储的图类型

void Init(ALGraph &G) //初始化图G
{
    for (int i = 0; i < G.vexnum; ++i) //为邻接表的顶点表初始化，默认顶点号从0一直到MaxVertexNum
        G.vertexes[i].vertex = i;
    return;
}

inline int find(ALGraph G, VertexType x) //寻找顶点x在顶点表中的位置(顶点号)；若x不存在，则返回-1
{
    for (int i = 0; i < MaxVertexNum; ++i) //遍历该邻接表的顶点表
        if (G.vertexes[i].vertex == x)
            return i;
    return -1;
}

//判断图G是否存在边<x,y>或(x,y)；若存在返回true，否则返回false
bool Adjacent(ALGraph G, VertexType x, VertexType y)
{
    int i = find(G, x);                                               //寻找顶点x在顶点表中的位置(顶点号)
    for (ArcNode *p = G.vertexes[i].first; p != nullptr; p = p->next) //遍历顶点x的边表。p为空则返回false，p不为空则进入循环体
        if (p->adjvex == y)
            return true;
    return false;
}

//若有向边<x,y>或无向边(x,y)不存在，则向图G中添加该边
bool AddEdge(ALGraph &G, VertexType x, VertexType y, int weight = 1)
{
    if (Adjacent(G, x, y)) //如果该边已存在，则返回false退出
        return false;

    //若该边不存在，则插入该边
    int i = find(G, x);                              //寻找顶点x在顶点表中的位置(顶点号)
    int j = find(G, y);                              //寻找顶点y在顶点表中的位置(顶点号)
    ArcNode *N = (ArcNode *)malloc(sizeof(ArcNode)); //创建新的边表结点(为即将插入的边表结点分配内存空间)
    if (G.vertexes[i].first == nullptr)              //判断此时顶点x是否已连接其他顶点。若没有连接，则即将插入的边将作为顶点x拉出的边表结点的首结点(直接在顶点后面插入)
    {
        //插入顶点N
        N->adjvex = y;
        N->weight = weight;
        N->next = nullptr;
        G.vertexes[i].first = N;
        return true;
    }
    else //如果此时顶点x已经连接了一些顶点
    {
        ArcNode *p;
        for (p = G.vertexes[i].first; p->next != nullptr; p = p->next) //找到从顶点x拉出的边表中指向最后一个边表结点的指针，以方便后续插入新边的操作
            ;
        //插入顶点N
        N->weight = weight;
        N->adjvex = y;
        N->next = nullptr;
        p->next = N;
        return true;
    }
    if (!G.DirStatue) //若该图为无向图，则还要把y到x的弧也连上
    {
        if (G.vertexes[j].first == nullptr) //如果此时顶点y没有连接其他顶点
        {
            //插入顶点N
            N->adjvex = x;
            N->weight = weight;
            N->next = nullptr;
            G.vertexes[j].first = N;
            return true;
        }
        else //如果此时顶点y已经连接了一些顶点
        {
            ArcNode *p;
            for (p = G.vertexes[j].first; p->next != nullptr; p = p->next) //找到从顶点y拉出的边表中指向最后一个边表的指针，以方便后续插入新边的操作
                ;
            //插入顶点N
            N->adjvex = x;
            N->weight = weight;
            N->next = nullptr;
            p->next = N;
            return true;
        }
    }
}

//求图G中顶点x的第一个邻接点，若有则返回指向该顶点的指针(即以该结点为弧尾的弧)。若x没有邻接点或图中不存在x，则返回nullptr
ArcNode *FirstNeighbor(ALGraph G, VertexType x)
{
    int i = find(G, x); //寻找顶点x在顶点表中的位置(顶点号)
    return G.vertexes[i].first;
}

//假设图G中顶点y是顶点x的一个邻接点，返回除y外指向顶点x的下一个邻接点的顶点，若y是x的最后一个邻接点，则返回nullptr
ArcNode *NextNeighbor(ALGraph G, VertexType x, VertexType y)
{
    int i = find(G, x); //寻找顶点x在顶点表中的位置(顶点号)
    ArcNode *p;
    for (p = G.vertexes[i].first; p->adjvex != y; p = p->next)
        ;
    return p->next;
}

//获取图G中边<x,y>或(x,y)对应的权值，若该边不存在则返回-1
EdgeType Get_edge_value(ALGraph G, VertexType x, VertexType y)
{
    int i = find(G, x); //寻找顶点x在顶点表中的位置(顶点号)
    ArcNode *p;
    for (p = G.vertexes[i].first; p != nullptr; p = p->next) //遍历顶点x的边表
        if (p->adjvex == y)
            return p->weight;
    return -1;
}